package com.wang.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: along
 * @Create: 2021/4/19 15:37
 * @Description:二叉搜索树的第k大节点
 */
public class Sword54 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    //解法一：中序遍历天然有序，用列表来存储，然后get第k大的值
    public int kthLargest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        process(root, list);
        return list.get(list.size() - k);
    }

    public void process(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        process(root.left, list);
        list.add(root.val);
        process(root.right, list);

    }
    //解法二：用两个类变量来记录进程和结果
    private int res = 0, cnt = 0;
    public int kthLargest1(TreeNode root, int k) {
        process(root, k);
        return res;
    }
    private void process(TreeNode root, int k) {
        if(root == null) return ;
        process(root.right, k);
        if(++cnt == k) {
            res = root.val;
        }
        process(root.left, k);
    }
}
